The advantages of using a network comprising switching elements which route packets of data through the network on the basis of an address contained within the packet are well known. Such networks are commonly called binary routing networks. In this type of a network, there exists only one unique path between any two network terminations. Such a network comprises a plurality of stages each having a number of switching nodes with the stages being interconnected by means of links. Upon receipt of a packet, each switching node is responsive to the contents of an address field to attempt to route the packet to the next stage via an interconnecting link. The receiving switching node first determines if the destination switching node in the next stage is capable of receiving a packet. If the switching node in the next stage is unable to receive a packet because the node has failed or is experiencing heavy traffic conditions, the receiving node waits indefinitely. Because of this provision, it is possible in a network such as that disclosed in the Jonathan S. Turner, U.S. Pat. No. 4,491,945, for a lockup condition to occur where the receiving node waits indefinitely or for a substantially long period of time for the downstream node to be capable of accepting any packet.
The loss of one packet from a message is not a disastrous occurrence in most packet switching protocols in present use. When a packet is lost, this loss is detected, and the message is merely retransmitted. However, portions of the network being locked up impedes not only just one message, but can gradually cause the packet carrying capacity of the entire network to deteriorate as more and more nodes are unable to transmit buffered packets.
Therefore, there exists a need for efficiently clearing deadlock conditions and for detecting the occurrence of a deadlock condition within the switching network.